package com.ocean.divideandconquer.easy;


import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/majority-element/
 * <p>
 * <p>
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * <p>
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例 2：
 * <p>
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 *  
 * <p>
 * 提示：
 * n == nums.length
 * 1 <= n <= 5 * 104
 * -109 <= nums[i] <= 109
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/24 <br>
 */
public class MajorityElement {

    public static void main(String[] args) {
        MajorityElement majorityElement = new MajorityElement();
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println(majorityElement.majorityElement3(nums));
        int[] nums2 = {3, 3, 4};
        int res = majorityElement.majorityElement3(nums2);
        System.out.println(res);
    }


    public int majorityElement3(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }

    public int majorityElementRec(int[] nums, int start, int end) {
        if (start >= end) {
            return nums[start];
        }
        int mid = start + (end - start) / 2;
        int left = majorityElementRec(nums, start, mid);
        int right = majorityElementRec(nums, mid + 1, end);
        if (left == right) {
            return left;
        }
        // 不相等就判断出现的次数
        int leftCount = count(nums, left, start, mid);
        int rightCount = count(nums, right, mid + 1, end);
        return leftCount > rightCount ? left : right;
    }

    private int count(int[] nums, int num, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }


    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int m = nums.length;
        for (int i = 0; i < m; i++) {
            int val = nums[i];
            map.put(val, map.getOrDefault(val, 0) + 1);
            if (map.get(val) > m / 2) {
                return val;
            }
        }
        return -1;
    }


    public int majorityElement2(int[] nums) {
        int element = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                element = num;
                count++;
                continue;
            }

            if (element == num) {
                count++;
            } else {
                count--;
            }
        }

        return element;
    }

}
